package triangulation;

import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import sample.Edge;
import sample.Vertex;




public class Triangulation {

	public static ArrayList<Triangle> triangleList;
	public static Polygon triangulationPolygon;
	
	public static Polygon triangulate(Polygon p){
		ArrayList<Vertex> tV1 = new ArrayList<Vertex>();
		triangleList = new ArrayList<Triangle>();
		triangulationPolygon = new Polygon();
		
		for(int i = 0 ; i < p.dcel.V1.size() ; i++){
			tV1.add(new Vertex(p.dcel.V1.get(i)));
		}
		
		int vs = tV1.size();
		int i = 0;

		while(vs > 3){

			if(!isCollinear(tV1.get((i)%vs),tV1.get((i+1)%vs),tV1.get((i+2)%vs))){
				
				if(!doesDiagonalIntersectPolygon(new Edge(tV1.get(i%vs), 
						tV1.get((i+2)%vs)), p.dcel.V1) && !(Polygon.orientationOfVertices(tV1.get((i)%vs),
								tV1.get((i+1)%vs),tV1.get((i+2)%vs)) ^ p.dcel.orientation)){
						
						//add each triangle of the triangulation to the triangle class
						triangleList.add(new Triangle(new Edge(tV1.get((i)%vs), tV1.get((i+1)%vs)), 
								new Edge(tV1.get((i)%vs), tV1.get((i+2)%vs)), 
								new Edge(tV1.get((i+1)%vs), tV1.get((i+2)%vs))));
						triangleList.get(triangleList.size()-1).label = triangleList.size();
						
						
						//add vertices and edges of triangulation to an instance of polygon class
						triangulationPolygon.addVertex(tV1.get((i)%vs));
						triangulationPolygon.addVertex(tV1.get((i+1)%vs));
						triangulationPolygon.addVertex(tV1.get((i+2)%vs));
						triangulationPolygon.connectVertices(tV1.get((i)%vs), tV1.get((i+1)%vs));
						triangulationPolygon.connectVertices(tV1.get((i)%vs), tV1.get((i+2)%vs));
						triangulationPolygon.connectVertices(tV1.get((i+1)%vs), tV1.get((i+2)%vs));

						tV1.remove(tV1.get((i+1)%vs));
						vs--;
					}
				}
			i++;
			
		}
		//last remaining triangle
		triangleList.add(new Triangle(new Edge(tV1.get(0), tV1.get(1)), 
				new Edge(tV1.get(0), tV1.get(2)), 
				new Edge(tV1.get(1), tV1.get(2))));
		triangleList.get(triangleList.size()-1).label = triangleList.size();
		
		//add remaining vertices and edges of triangulation to an instance of polygon class
		triangulationPolygon.addVertex(tV1.get(0));
		triangulationPolygon.addVertex(tV1.get(1));
		triangulationPolygon.addVertex(tV1.get(2));
		triangulationPolygon.connectVertices(tV1.get(0), tV1.get(1));
		triangulationPolygon.connectVertices(tV1.get(0), tV1.get(2));
		triangulationPolygon.connectVertices(tV1.get(1), tV1.get(2));
		
		//print triangle
//		for(int k = 0 ; k < triangleList.size() ; k++){
//			System.out.println(triangleList.get(k));
//		}
		
		tV1.clear();
		return triangulationPolygon;
	}
	
	public static boolean isCollinear(Vertex v1, Vertex v2, Vertex v3){
		return areaOfThreePoints(v1, v2, v3) == 0;
	}
	
	public static int areaOfThreePoints(Vertex v1, Vertex v2, Vertex v3)
	{
		return (int) ((v2.getX() - v1.getX()) * (v3.getY() - v1.getY())
				- (v3.getX() - v1.getX()) * (v2.getY() - v1.getY()));
	}
	
	public static boolean doesDiagonalIntersectPolygon(Edge e, ArrayList<Vertex> vlist){
		for(int i = 0 ; i < vlist.size() ; i++){
			if(Intersection.areEdgesIntersect(e, 
					new Edge(vlist.get(i),vlist.get((i+1)%vlist.size())))){
//					System.out.println("edges intersects ="+e+" and "+new Edge(vlist.get(i),vlist.get((i+1)%vlist.size())));
					return true;
			}
		}
		return false;
	}
	
	public static boolean doesEdgeIntersectPolygonExceptGuardedEdge(Edge e, ArrayList<Vertex> vlist, Edge guardEdge){
		for(int i = 0 ; i < vlist.size() ; i++){
			Edge e2= new Edge(vlist.get(i),vlist.get((i+1)%vlist.size()));
			if(Intersection.areEdgesIntersect(e, e2) && guardEdge != null && !e2.equals(guardEdge)){
//					System.out.println("edges intersects ="+e+" and "+new Edge(vlist.get(i),vlist.get((i+1)%vlist.size())));
					return true;
			}
		}
		return false;
	}
	
	

	
	public static void draw(Graphics g)
	{
		triangulationPolygon.draw(g, Color.BLACK);
		triangulationPolygon.drawVertices(g, Color.BLACK);
	}
}
